package day_2022_12_to_3.year2023;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @author haomin
 * @date 2023/03/25 09:11
 **/
public class Day3_25_Review {
    public static final ThreadLocalRandom random = ThreadLocalRandom.current();

    public static void main(String[] args) {
        int[] arr = new int[100];
        for(int i = 0; i < 100; ++i) {
            arr[i] = random.nextInt(0, 100);
        }
        int[] arr2 = Arrays.copyOf(arr, arr.length);
        int[] arr3 = Arrays.copyOf(arr, arr.length);
        int[] arr4 = Arrays.copyOf(arr, arr.length);

        long start, end;
//        start = System.nanoTime();
//        quickSort1(arr, 0, arr.length-1);
//        end = System.nanoTime();
//        System.out.println("耗时：" + (end-start)/1000000.0 + "ms " + isOrder(arr));

        start = System.nanoTime();
        quickSort2(arr2, 0, arr2.length-1);
        end = System.nanoTime();
        System.out.println("耗时：" + (end-start)/1000000.0 + "ms " + isOrder(arr2));

        start = System.nanoTime();
        quickSort3(arr3, 0, arr3.length-1);
        end = System.nanoTime();
        System.out.println("耗时：" + (end-start)/1000000.0 + "ms " + isOrder(arr3));

        start = System.nanoTime();
        quickSort4(arr4, 0, arr4.length-1);
        end = System.nanoTime();
        System.out.println("耗时：" + (end-start)/1000000.0 + "ms " + isOrder(arr4));
    }

    // 一路快排 （当重复数据过多会造成堆栈溢出）
    private static void quickSort1(int[] arr, int l, int r) {
        if(l >= r) return;
        int p = partition1(arr, l, r);
        quickSort1(arr, l, p-1);
        quickSort1(arr, p+1, r);
    }

    private static int partition1(int[] arr, int l, int r) {
        int randomInd = random.nextInt(l, r);
        swap(arr, l, randomInd);
        int v = arr[l];
        int j = l;
        int i = l+1;
        for(; i <= r; ++i) {
            if(arr[i] < v) {
                swap(arr, i, j+1);
                j++;
            }
        }
        swap(arr, l, j);
        return j;
    }

    // 二路快排
    private static void quickSort2(int[] arr, int l, int r) {
        if(l >= r) return;
        int p = partition2(arr, l, r);
        quickSort2(arr, l, p-1);
        quickSort2(arr, p+1, r);
    }

    private static int partition2(int[] arr, int l, int r) {
        int randomInd = random.nextInt(l, r);
        swap(arr, l, randomInd);
        int v = arr[l];
        int i = l + 1;
        int j = r;
        while(true) {
            while (i <= j && arr[i] < v) i++;
            while (i <= j && arr[j] > v) j--;
            if(i >= j) break;
            swap(arr, i, j);
            i++; j--;
        }
        swap(arr, l, j);
        return j;
    }

    // 三路快排 （二路快排优化）
    private static void quickSort3(int[] arr, int l, int r) {
        if(l >= r ) return;
        int randomInd = random.nextInt(l, r);
        swap(arr, randomInd, l);
        int v = arr[l];
        int lt = l;
        int i = lt+1;
        int gt = r+1;
        while(i < gt) {
            if(arr[i] < v) {
                swap(arr, lt+1, i);
                lt++;
                i++;
            }else if(arr[i] > v) {
                swap(arr, gt-1, i);
                gt--;
            }else i++;
        }
        swap(arr, l, lt);
        quickSort3(arr, l, lt-1);
        quickSort3(arr, gt, r);
    }

    // 挖坑法
    private static void quickSort4(int[] arr, int l, int r) {
        if(l >= r) return;
        int p = partition4(arr, l, r);
        quickSort4(arr, l, p-1);
        quickSort4(arr, p+1, r);
    }

    private static int partition4(int[] arr, int l, int r) {
        int v = arr[l];
        int i = l;
        int j = r;
        while (i < j) {
            while (i < j && arr[j] >= v) j--;
            arr[i] = arr[j];
            while (i < j && arr[i] <= v) i++;
            arr[j] = arr[i];
        }
        arr[i] = v;
        return i;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static boolean isOrder(int[] arr) {
        for(int i = 0; i < arr.length-1; ++i) {
            if(arr[i] > arr[i+1]) return false;
        }
        return true;
    }
}